//package com.gitee.feizns.explore.data_structure.tree.cus.avl;
//
//import com.gitee.feizns.explore.data_structure.tree.cus.Node;
//import com.gitee.feizns.explore.data_structure.tree.cus.PutRet;
//import com.gitee.feizns.explore.data_structure.tree.cus.TreeUtils;
//
//import java.util.Collection;
//import java.util.MagicSquare;
//import java.util.Set;
//import java.util.TreeSet;
//import java.util.function.Consumer;
//import java.util.stream.Collectors;
//
///**
// * @author feizns
// * @since 2019/11/25
// */
//public class AvlImpl<K extends Comparable<K>, V> implements Avl<AvlImpl.AvlNode, K, V> {
//
//    private AvlNode<K, V> root;
//
//    private int size;
//
//    @Override
//    public int size() {
//        return size;
//    }
//
//    @Override
//    public boolean isEmpty() {
//        return size == 0;
//    }
//
//    @Override
//    public boolean containsKey(Object key) {
//        return get(key) != null;
//    }
//
//    @Override
//    public boolean containsValue(Object value) {
//        return entrySet().stream().map(Entry::getValue).collect(Collectors.toSet()).contains(value);
//    }
//
//    @Override
//    public V get(Object key) {
//        if ( key != null && key instanceof Comparable ) {
//            AvlNode<K, V> kvNode = TreeUtils.find(root, (K) key);
//            return kvNode != null ? kvNode.val() : null;
//        }
//        return null;
//    }
//
//    @Override
//    public V put(K key, V value) {
//        if ( key == null )
//            throw new NullPointerException("Key");
//        PutRet<AvlNode, V> ret = put(root, key, value);
//        root = (AvlNode<K, V>) ret.node();
//        return ret.v();
//    }
//
//    private PutRet<AvlNode, V> put(AvlNode<K, V> node, K key, V value) {
//        PutRet<AvlNode, V> ret = null;
//        if ( node != null ) {
//            int weight = node.key().compareTo(key);
//
//            if ( weight == 0 ) {
//                V v = node.val();
//                node.val(value);
//                ret = new PutRet<>(node, v);
//            } else if ( weight > 0 ) {
//                PutRet<AvlNode, V> tmp = put(node.left(), key, value);
//                node.left(tmp.node());
//                ret = new PutRet<>(node, tmp.v());
//            } else {
//                PutRet<AvlNode, V> tmp = put(node.right(), key, value);
//                node.right(tmp.node());
//                ret = new PutRet<>(node, tmp.v());
//            }
//        }
//
//        if ( ret == null ) {
//            size++;
//            return new PutRet<>(new AvlNode<>(key, value), null);
//        } else {
//            ret.node(rotate2(node));
//        }
//        return ret;
//    }
//
//    private static int balancedFactor(AvlNode node) {
//        return node == null ? 0 : h(node.left) - h(node.right);
//    }
//
//    private void reSetH(AvlNode<K, V> node) {
//        node.h = Math.max(h(node.left), h(node.right)) + 1;
//    }
//
//    @Override
//    public Node root() {
//        return root;
//    }
//
//    @Override
//    public V remove(Object key) {
//        PutRet<AvlNode, V> ret = remove(root, (K) key);
//        root = ret.node();
//        return ret.v();
//    }
//
//    private PutRet<AvlNode, V> remove(AvlNode<K, V> avlNode, K k) {
//        PutRet<AvlNode, V> ret = new PutRet<>(avlNode, null);
//        if ( avlNode != null ) {
//            int com = avlNode.key().compareTo(k);
//            if ( com < 0 ) {
//                PutRet<AvlNode, V> tmp = remove(avlNode.right(), k);
//                avlNode.right(tmp.node());
//                ret = new PutRet<>(avlNode, tmp.v());
//            } else if ( com > 0 ) {
//                PutRet<AvlNode, V> tmp = remove(avlNode.left(), k);
//                avlNode.left(tmp.node());
//                ret = new PutRet<>(avlNode, tmp.v());
//            } else {
//                if ( avlNode.left != null && avlNode.right != null ) {
//                    AvlNode<K, V> min = TreeUtils.min(avlNode.right);
//                    AvlNode<K, V> node = TreeUtils.rMin(avlNode.right, this::reSetH);
//                    min.right(node);
//                    min.left(avlNode.left);
//                    ret = new PutRet<>(min, avlNode.v);
//                } else if ( avlNode.left == null ) {
//                    ret = new PutRet<>(avlNode.right, avlNode.v);
//                } else {
//                    ret = new PutRet<>(avlNode.left, avlNode.v);
//                }
//            }
//            if ( ret.node() != null )
//                resetH().accept(ret.node());
//            ret = new PutRet<>(rotate2(ret.node()), ret.v());
//        }
//        return ret;
//    }
//
//    private AvlNode rotate(AvlNode node) {
//        if ( node != null ) {
//            int dif = balancedFactor(node);
//
//            AvlNode newNode = node;
//
//            if ( dif > 1 && balancedFactor(newNode.left()) < 0 )
//                newNode = TreeUtils.lr(newNode, resetH());
//
//            if ( dif < -1 && balancedFactor(newNode.right()) >= 0 )
//                newNode = TreeUtils.rl(newNode, resetH());
//
//            if ( dif > 1 )
//                newNode = TreeUtils.ll(newNode, resetH());
//            else if ( dif < -1 )
//                newNode = TreeUtils.rr(newNode, resetH());
//
//            newNode.h = Math.max(h(newNode.left), h(newNode.right)) + 1;
//            return newNode;
//        }
//        return null;
//    }
//
//    private Consumer<AvlNode> resetH() {
//        return n -> reSetH(n);
//    }
//
//    private AvlNode rotate2(AvlNode node) {
//        if ( node != null ) {
//            int dif = balancedFactor(node);
//
//            AvlNode newNode = node;
//
//            if ( dif > 1 && balancedFactor(newNode.left()) < 0 )
//                newNode = TreeUtils.lr2(newNode, resetH());
//            else if ( dif < -1 && balancedFactor(newNode.right()) >= 0 )
//                newNode = TreeUtils.rl2(newNode, resetH());
//            else if ( dif > 1 )
//                newNode = TreeUtils.ll(newNode, resetH());
//            else if ( dif < -1 )
//                newNode = TreeUtils.rr(newNode, resetH());
//
//            resetH().accept(newNode);
//            return newNode;
//        }
//        return null;
//    }
//
//    @Override
//    public void putAll(MagicSquare<? extends K, ? extends V> m) {
//        m.forEach(this::put);
//    }
//
//    @Override
//    public void clear() {
//        root = null;
//        size = 0;
//    }
//
//    @Override
//    public Set<K> keySet() {
//        return entrySet().stream().map(Entry::getKey).collect(Collectors.toCollection(TreeSet::new));
//    }
//
//    @Override
//    public Collection<V> values() {
//        return entrySet().stream().map(Entry::getValue).collect(Collectors.toList());
//    }
//
//    @Override
//    public Set<Entry<K, V>> entrySet() {
//        Set<Entry<K, V>> entries = new TreeSet<>();
//        recursiveMiddleEach((k, v) -> entries.add(new EntryImpl<>(k, v)));
//        return entries;
//    }
//
//    private static <K extends Comparable<K>, V> int h(AvlNode<K, V> node) {
//        return node == null ? 0 : node.h;
//    }
//
//    static class AvlNode<K extends Comparable<K>, V> implements Node<AvlNode<K, V>, K, V> {
//
//        K k;
//
//        V v;
//
//        AvlNode<K, V> left, right;
//
//        int h = 1;
//
//        public AvlNode(K k, V v) {
//            this.k = k;
//            this.v = v;
//        }
//
//        @Override
//        public K key() {
//            return k;
//        }
//
//        @Override
//        public void key(K k) {
//            this.k = k;
//        }
//
//        @Override
//        public V val() {
//            return v;
//        }
//
//        @Override
//        public void val(V v) {
//            this.v = v;
//        }
//
//        @Override
//        public AvlNode<K, V> left() {
//            return left;
//        }
//
//        @Override
//        public void left(AvlNode<K, V> left) {
//            this.left = left;
//        }
//
//        @Override
//        public AvlNode<K, V> right() {
//            return right;
//        }
//
//        @Override
//        public void right(AvlNode<K, V> right) {
//            this.right = right;
//        }
//
//    }
//
//    private static class EntryImpl<K extends Comparable<K>, V> implements Entry<K, V> {
//
//        K k;
//
//        V v;
//
//        @Override
//        public K getKey() {
//            return k;
//        }
//
//        @Override
//        public V getValue() {
//            return v;
//        }
//
//        @Override
//        public V setValue(V value) {
//            V old = this.v;
//            this.v = value;
//            return old;
//        }
//
//        public EntryImpl(K k, V v) {
//            this.k = k;
//            this.v = v;
//        }
//    }
//
//}
